//https://www.bilibili.com/video/BV1mt4y1s7H1/?spm_id_from=333.337.search-card.all.click&vd_source=4ec910f05eea76e8fe7255f381962332
//https://github.com/fuxuemingzhu/Leetcode-Solution-All/blob/main/100-199/152.%20Maximum%20Product%20Subarray%20%E4%B9%98%E7%A7%AF%E6%9C%80%E5%A4%A7%E5%AD%90%E6%95%B0%E7%BB%84.md
//乘积最大的子数组.cpp-152
//https://leetcode.cn/problems/maximum-product-subarray/?envType=study-plan-v2&envId=top-100-liked
//求连续子数组最大乘积。

#include <vector>
#include <stack>
#include <list>
#include <map>
#include <string>
#include <unordered_map>
#include <algorithm>

using namespace std;

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        if (nums.empty()) return 0;
        int cur_max=nums[0],cur_min=nums[0],res=cur_max;
        for(int i=1;i<nums.size();++i){
            int cur=nums[i];
            int tmp_max=max(cur,max(cur_max*cur,cur_min*cur));
            cur_min=min(cur,min(cur_max*cur,cur_min*cur));
            cur_max=tmp_max;
            res=max(res,cur_max);
        }
        return res;
    }
};
class Solution2 {
public:
    int maxProduct(vector<int>& nums) {
        vector <long> maxF(nums.begin(),nums.end()), minF(nums.begin(), nums.end());
        for (int i = 1; i < nums.size(); ++i) {
            maxF[i] = max(maxF[i - 1] * nums[i], max((long)nums[i], minF[i - 1] * nums[i]));
            minF[i] = min(minF[i - 1] * nums[i], min((long)nums[i], maxF[i - 1] * nums[i]));
            // if(minF[i]<INT_MIN) {
            //     minF[i]=nums[i];
            // }
        }
        return *max_element(maxF.begin(), maxF.end());
    }
};
